Casper CBC: Justification

justification consists of sender's latest messages from each validator and receiver's current state

description

Actually justification is (the hashes of) the latest messages from each validator, so we need to reconstruct sender's state (to be used in LMD Ghost, etc) with the sender's message history stored in the receiver. Then justification is consisted of sender's latest messages and (a part of) receiver's state. Is it reasonable?

After all, what is the justification in practice?

I think inclusion of other last message in the justification is something that should be required anyways.

Aka - the justification should commit to every message that the validator has seen before - which includes messages it made itself

justifications are essentially just a dictionary from validator => the last message you've seen from that validator. they essentially are a committment to "what I've seen as I'm creating this message"

how are the justifications communicated efficiently between validators - is it like i send a hash of all the hashes of the latest messages i have from the other validators? (what a mouthful!)

so currently, yeah, it's essentially just the hashes of the latest messages

but there are ways of making that much more efficient

We can essentially make it so you don't have send most of it (calling it, for now, the "minimized justification"), as you "implicitly" commit to it.

Haven't really formalized it though

Justifications need to be a dict that maps validator => set(messages), so validators can show other validators equivocations they want. We might also want to add more information to these justifications (such as if message is valid, etc).

Well, but if we require each block created by validator to contain a snapshot of a blockdag maintained by at the moment of creating , are these blocks going to become large and keep growing forever? This immediately looks like a major performance problem. The issue address by evolving the blockdag only by appending new blocks. If every block can point to blocks seen at its creation - we will call these pointers justifications - then we can just use reduce the required collection of pointers to just roots of the blockdag's snapshot.

Unrealistic liveness?

Currently, the simulation gives us "unrealistic liveness" as the most recent messages from each validator in the global view are the only messages that propagate (this combined w/ justifications containing the messages is a very unrealistic combination). We should send messages more realistically, by sampling from messages that a validator has not seen.

When sending a message from validator V1 to validator V2, sample randomly from the messages V1 has created that V2 has seen, rather than just sending the latest message. Message generation does not have to change, but there can be a step where these pairs of validators sample some int between sequence number of current message and sequence of last seen message, then choose the message with this sequence number to send.

What if I've received a message that has messages in it' justification I've not seen yet?

So note: if you have receive a message that has messages in it's justification you have not seen yet, then you should store that message in a "pending" place - until you receive the rest of the messages in it's justification.

Python Poc

Pending messages are stored in view, when maybe they should not be. The view is storing everything that exists.

CasperLabs

Note that it's possible that the validator has not seen all (or any) parents of a proposed block. In this case the proposed block is saved in a buffer where it can be validated after arrival of all parents.

A block can only be added to the blockdag if all justifications of were collected and added before . So if a validator receives a block before receiving some of its justifications, the received block must wait in the buffer.

questions

How to implement justification in realistic situation?

To be exact, what is the relationship between liveness and such justification?

How to recover this from just a hash?

references